class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        # 创建一个集合，方便快速查找单词是否在字典中
        word_set = set(wordDict)
        
        # 初始化动态规划数组，dp[i] 表示 s[:i] 是否可以被拼接
        dp = [False] * (len(s) + 1)
        dp[0] = True  # 空字符串可以被拼接
        
        # 遍历字符串的每个位置
        for i in range(1, len(s) + 1):
            # 尝试从 0 到 i 的所有可能分割点
            for j in range(i):
                # 如果 s[:j] 可以被拼接，并且 s[j:i] 在字典中
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break  # 找到一个有效的分割点即可
        
        return dp[len(s)]
    
# 示例测试
solution = Solution()
print(solution.wordBreak("leetcode", ["leet", "code"]))  # 输出: True
print(solution.wordBreak("applepenapple", ["apple", "pen"]))  # 输出: True
print(solution.wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))  # 输出: False